Heap.java

packagesection17_Heap;

importjava.util.ArrayList;
//import java.util.Collections;

publicclassHeap {

ArrayList<Integer> data = newArrayList<>();

publicvoidadd(intitem) {
data.add(item);

upheapify(data.size() - 1);
 }

privatevoidupheapify(intchildIndex) {
intparentIndex = (childIndex - 1) / 2;

if (data.get(childIndex) < data.get(parentIndex)) {
// Collections.swap(data, childIndex, parentIndex);
this.swap(childIndex, parentIndex);
upheapify(parentIndex);
 }
 }

privatevoidswap(inti, intj) {
intithVal = data.get(i);
intjthVal = data.get(j);

data.set(i, jthVal);
data.set(j, ithVal);
 }

publicvoiddisplay() {
System.out.println(data);
 }

publicintsize() {
returnthis.data.size();
 }

publicbooleanisEmpty() {
returnthis.size() == 0;
 }

publicintremove() throwsException {
if (this.size() == 0)
thrownewException("No elements to remove...");

intremovedItem = data.get(0);

this.swap(0, this.size() - 1);
data.remove(this.size() - 1);

downheapify(0);

returnremovedItem;
 }

// clean code
publicvoiddownheapify(intpi) {
intlci = 2 * pi + 1;
intrci = 2 * pi + 2;

intminIndex = pi;

if (lci < this.size() && data.get(lci) < data.get(minIndex))
minIndex = lci;

if (rci < this.size() && data.get(rci) < data.get(minIndex))
minIndex = rci;

if (minIndex != pi) {
swap(minIndex, pi);
downheapify(minIndex);
 }
 }

/*
 private void downheapify2(int parentIndex) {
 int leftChildIndex = (2 * parentIndex) + 1;
 int rightChildIndex = (2 * parentIndex) + 2;

 if (leftChildIndex >= this.size() && rightChildIndex >= this.size())
 return;

 int leftChild = -1, rightChild = -1;
 int parentData = data.get(parentIndex);

 if (leftChildIndex < this.size())
 leftChild = data.get(leftChildIndex);

 if (rightChildIndex < this.size())
 rightChild = data.get(rightChildIndex);

 if (leftChild == -1 && rightChild == -1)
 return;

 if (parentData > leftChild || parentData > rightChild) {

 if (rightChild == -1) {
 this.swap(parentIndex, leftChildIndex);
 downheapify2(leftChildIndex);

 } else {
 int minVal = Math.min(leftChild, rightChild);
 int minIndex = minVal == leftChild ? leftChildIndex : rightChildIndex;

 this.swap(parentIndex, minIndex);

 downheapify2(minIndex);
 }
 }
 }
*/

publicintget() {
returnthis.data.get(0);
 }
}